.TL
Codes
.AU
strlst
.NH 1
general polynomial code
.EQ
gsize -1
define repr `~ sub { ~$3 } ($1) sub { $2~ }`
define code `~ sub { $2 } ($1)`
define bin `~ ($1) sub { 2 }`
define is `~=~`
delim $$
.EN
.SH
the task
.PP
Assuming a message $ m is bin(0011) $ and a generator $ G(x) is x sup 2 + x + 1 $, find the codeword $ t is C sub t is code(m, C) $ of the polynomial code $ C $.
.SH
the solution
.PP
The resulting codeword $ 2 $ has $ m + r $ bits, where $ r $ is equal to the highest polynomial degree of $ C $, in this case $ 2 $. For calculations using polynomials, our original message $ m $ is transformed into a polynomial:
.EQ
M(x) is 0 times x sup 3 + 0 times x sup 2 + 1 times x sup 1 + 1 times x sup 0 is x + 1
.EN
.PP
Our resulting codeword $ t $, also represented as a polynomial $ t is T(x) $ is the result of the operation:
.EQ
T(x) is x sup r times M(x) - R(x)
.EN
.PP
This other newly introduced polynomial, $ R(x) $, is meant to represent the rest of the division of $ (x sup r times M(x) ) $ and $ G(x) $, or more generally:
.EQ
R(x) is { x sup r times M(x) } ~mod~ G(x)
.EN
.PP
It is instantly obvious that this calculation requires the infamous polynomial division. It is to note though, all operations are implicity taken modulo 2. Formally, we can denote polynomial division like this:
.EQ
x sup r times M(x) is x sup 2 times (x + 1) is x sup 3 + x sup 2
.EN
.ft CW
.EX
    (x^3 + x^2) mod (x^2 + x + 1) = x + 1
  +  x^3 +   0 + x
 ----------------------
       0 + x^2 + x + 1
         + x^2 + x + 1
 ----------------------
             0 + 0 + 0 = 0R
.EE
.ft
.EQ
R(x) is (x sup 3 + x sup 2 ) ~mod~ (x sup 2 + x + 1) is 0
.EN
.PP
Finally we calculate $ T(x) $, which we said is the following:
.EQ
T(x) is x sup r times M(x) - R(x) is (x sup 3 + x sup 2 ) - 0 = x sup 3 + x sup 2
.EN
.PP
Because the initial task was to calculate the codeword $ t $ in binary form, we can reformulate our result to yield not a polynomial representation, but a binary one:
.EQ
t is T(x) is x sup r times M(x) is bin(2 sup 1+r + 2 sup 0+r ) is bin(2 sup 3 + 2 sup 2 ) is bin(0011 bold 00 ) 
.EN
.NH 2
error correction using polynomial codes
.NH 1
CRC
